package io.github.hadyang.leetcode.tencent;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;

public class Array895 {

  @Test
  public void test() {
    int[] nums1 = new int[] {1, 2};
    int[] nums2 = new int[] {3, 4};

    System.out.println(findMedianSortedArrays(nums1, nums2));

    nums1 = new int[] {1, 3};
    nums2 = new int[] {2};

    System.out.println(findMedianSortedArrays(nums1, nums2));

    nums1 = new int[] {};
    nums2 = new int[] {2, 3};

    System.out.println(findMedianSortedArrays(nums1, nums2));

    nums1 = new int[] {1};
    nums2 = new int[] {2, 3, 4};

    System.out.println(findMedianSortedArrays(nums1, nums2));
  }

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    List<Integer> data = new ArrayList<>();

    int i = 0, j = 0;
    while (i < nums1.length || j < nums2.length) {
      if (i >= nums1.length) {
        data.add(nums2[j++]);
        continue;
      }

      if (j >= nums2.length) {
        data.add(nums1[i++]);
        continue;
      }

      if (nums1[i] > nums2[j]) {
        data.add(nums2[j]);
        j++;
      } else {
        data.add(nums1[i]);
        i++;
      }
    }

    if (data.size() == 1) {
      return data.get(0);
    }

    int mid = data.size() / 2;
    if (data.size() % 2 == 0) {
      return (data.get(mid - 1) + data.get(mid)) * 1.0 / 2;
    } else {
      return data.get(mid);
    }
  }
}
